/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.leetCode._1_Array_Linked_List;

import com.leetCode.structure.ListNode;
import static com.leetCode.structure.ListNode.*;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/5/10
 */
//Hard
public class _05_25_ReverseNodesInKGroup {

    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode result = head;
        for (int i = 0; i < k - 1; i++) {
            result = result.next;
            if (result == null) {
                return head;
            }
        }
        ListNode[] pair = new ListNode[k];
        ListNode pre = null;
        ListNode next;
        ListNode cur = head;
        ListNode temp;
        while (cur != null) {
            pair[0] = cur;
            temp = cur;
            for (int i = 0; i < k - 1; i++) {
                if (temp.next == null) {
                    return result;
                }
                temp = temp.next;
            }
            for (int i = 0; i < k - 1; i++) {
                pair[i + 1] = pair[i].next;
            }
            if (pre != null) {
                pre.next = pair[k - 1];
            }
            next = pair[k - 1].next;
            for (int i = k - 1; i > 0; i--) {
                pair[i].next = pair[i - 1];
            }
            cur.next = next;
            pre = cur;
            cur = next;
        }
        return result;
    }

//    !_!
//    ?_?
    public static ListNode reverseKGroup1(ListNode head, int k) {
        ListNode endNode = nextKNode(head, k);
        if (endNode == null) {
            return head;
        }
        ListNode nextHead = reverseKGroup1(endNode.next, k);

        reverseKNode(head, k);
        head.next = nextHead;
        return endNode;
    }

    private static ListNode reverseKNode(ListNode head, int k) {
        if (k > 1) {
            ListNode next = reverseKNode(head.next, k - 1);
            next.next = head;
        }
        return head;
    }

    private static ListNode nextKNode(ListNode node, int k) {
        while (--k > 0 && node != null) {
            node = node.next;
        }
        return node;
    }

    public static void main(String[] args) {
        ListNode head = build(new int[]{1, 2, 3, 4, 5});
        System.out.println(str(reverseKGroup1(head, 2)));
        head = build(new int[]{1, 2, 3, 4, 5});
        System.out.println(str(reverseKGroup1(head, 3)));
    }
}
